#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
private:
    int get_dp(vector<int>& costs, int i) {
        if (i < 0) {
            return 0;
        }
        return costs[i];
    }
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dp(days.back() + 1);
        unordered_set<int> set(days.begin(), days.end());
        for (int i = 1; i < dp.size(); i++) {
            if (set.find(i) == set.end()) {
                dp[i] = dp[i - 1];
            } else {
                int min_cost = dp[i - 1] + costs[0];
                min_cost = min(min_cost, get_dp(dp, i - 7) + costs[1]);
                min_cost = min(min_cost, get_dp(dp, i - 30) + costs[2]);
                dp[i] = min_cost;
            }
        }
        return dp.back();
    }
};